package three;

public class A049 {



    int ret=Integer.MIN_VALUE;
    //计算以该节点开时，递归以下的最大值，到达每个节点都比较一下
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ret;
    }
    public int dfs(TreeNode root) { //返回值：以根节点向左或者向右最大值的一条路，左右只能选一个，是否就会和该根节点的父节点形成Y字型
        if(root==null) return 0;
        //1.记录到该节点的最大值
        int key = root.val;
        int l = Math.max(dfs(root.left),0);
        int r = Math.max(dfs(root.right),0);
        //记录结果要考虑正负数的情况
        ret = Math.max(ret,key+l+r);
        return Math.max(l,r)+key;
    }
}
